package com.leetcode.dynamic_programming;

/**
 * @author Dennis Li
 * @date 2020/7/20 22:49
 */
public class MaxProfit_121 {

    // 暴力解法
    public static int maxProfit(int[] prices) {
        int len = prices.length;
        if(len == 0) return 0;
        int max = Integer.MIN_VALUE;
        for (int i = 1; i < len; i++) {
            for (int j = 0; j < i; j++) {
                max = Math.max(max, prices[i] - prices[j]);
            }
        }
        return max;
    }

    // DP一次遍历,空间O(1)
    public int maxProfit2(int[] prices) {
        int len = prices.length;
        if(len == 0) return 0;
        int min = Integer.MAX_VALUE;
        int pre = 0;
        for (int i = 1; i < len; i++) {
            min = Math.min(min, prices[i - 1]);
            pre = Math.max(pre, prices[i] - min);
        }
        return pre;
    }

}
